1. Field of the Invention
This invention relates to mediating the use of a computer resource by multiple events that seek to use the computer resource at the same time and, in particular, that seek to use the computer resource at times that are not known until access to the computer resource is sought.
2. Related Art
A computer includes a variety of mechanisms for performing various operations in accordance with achieving the functionality of the computer. (Herein, "computer" can refer to any computational device). Such mechanisms can be referred to as "computer resources."
During use of a computer, various operations ("events") occur in response to stimuli originating in various parts of the computer system and associated hardware, each of which can cause use of one or more computer resources. An "event" is an execution context that is entered into and interrupts a current execution context. An "execution context" is the minimal computer system state and program counter location information that needs to be preserved in order to allow the operating system to switch among different paths of instruction execution. An event may necessitate use of a computer resource while that resource is already in use, either in the context of the main program flow of the computer system or in response to a prior event. Further, the need of the event to use the computer resource will generally not be known until access to the computer resource is sought by the event. Additionally, some computer resources cannot be simultaneously used by multiple events. In such situations, it is necessary to mediate use of the computer resource by the events.
Such mediation can be accomplished using synchronization services (e.g., "mutex," "semaphore" or "critical section" services, as known to those skilled in the art) provided by the operating system of the computer. Each event is associated with a "thread" (processor execution context). A sequence of instructions being executed by the computer, and the hardware context associated therewith, is termed a "thread," of which there can be several in a computer system. Only one thread executes on a processor at a time. The general implementation of modern operating systems is to have a scheduling and dispatching algorithm select from the available pending contexts one which is to be made active. At that time, the context is made the current context, where the state includes where the processor should continue executing instructions. The processor is then said to be executing the "current thread." Each event that occurs is associated with a "thread," but not necessarily a specific or predictable thread. That is, an event may occur in response to an external stimulus causing an interrupt of the processor and this may cause instructions to be executed which preserve some minimal state or context of the current thread, and then transfer control to a different program counter location. Additional levels of complexity in scheduling may be present such that the event is queued for later processing, but that later processing may still interrupt the normal flow of control associated with the current thread. The salient characteristic of event handling is that it causes the current program location of a thread to be saved and the processor to start executing different instructions associated with the particular event. At some point, the instructions stream for handling the event causes a return to the instructions stream associated with the thread that was interrupted. When an event ("pre-empting event") seeks to use a resource that is already being used by another event ("executing event"), the thread of which the pre-empting event is part is stopped until the thread including the event that is using the resource is finished using that resource.
However, when an event seeks to use a resource that is already in use, it may not be possible to use operating system synchronization services. For example, the resource may be in use by an event already, with the two events sharing a single thread for the purposes of the operating system's synchronization services. If the pre-empting event causes the operating system to stop dispatching of the thread, then the processing for the first event cannot complete. Since the pre-empting event is waiting for the first event to complete, the thread will have entered the state known as "deadlock." Additionally, some operating systems explicitly forbid the use of synchronization services when processing events. This makes it highly desirable to devise a mechanism which will mediate among multiple events competing for use of the same resource.